/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2021并保留所有权利。
 * Copyright 2021, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */
/** 
* @Description: 1, match3是match4的升级版，看起来更高大上一点有么有😄
 * 2,char 类型时用' '单引号
 * 3，match1--暴力破解法    match2--字符串转化为char数组+for each 方法
 * +stack push相反符号的方法
 * match3 -- hashmap存储左右符号为key,value，使用map.containsKey()方法
 * 进行stack  push+map.get()方法做相反符号的判断。
 * match4 --match3的降级版 
* @Param: @param null 
* @return:  
* @Author: itdebug
* @Date: 2021/1/5 
*/ 
package com.azdebugit.matcher;

import java.util.HashMap;
import java.util.Stack;

public class match {
	public boolean match1(String s) {

		if (s.contains("()") || s.contains("[]") || s.contains("{}")) {
			s = s.replace("()", "");
			s = s.replace("[]", "");
			s = s.replace("{}", "");
			return s.length() == 0;
		} else {
			return false;
		}
	}

	public boolean match2(String s) {
		Stack<Character> stack = new Stack<Character>();
		char[] arr = s.toCharArray();
		for (char c : arr) {
			if (c == '(') {
				stack.push(')');
			} else if (c == '[') {
				stack.push(']');
			} else if (c == '{') {
				stack.push('}');
			} else {
				if (stack.isEmpty() || stack.pop() != c) {
					return false;
				}

			}
		}
		return stack.isEmpty();

	}
	public boolean match3(String s) {
		Stack<Character> stack = new Stack<Character>();
		HashMap<Character, Character> map = new HashMap<Character, Character>();
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');
		
		for(int i=0;i<s.length();i++){
			char ch = s.charAt(i);
			if(map.containsKey(ch)) {
				stack.push(ch);
			}
			else {
				if(stack.isEmpty() ) {
					return false;
				}
				else {
					char ele = stack.pop();
					if(ch!=map.get(ele) ) {
						return false;
					}
				}
			}
		}
		return stack.isEmpty();
	}
public boolean match4(String s) {
	Stack<Character> stack = new Stack<Character>();
	for(int i=0;i<s.length();i++){
		char ch = s.charAt(i);
		if(ch=='('||ch=='['||ch=='{') {
			stack.push(ch);
		}
		else {
			if(stack.isEmpty() ) {
				return false;
			}
			else {
				char ele = stack.pop();
				if(ele=='('&&ch!=')' || ele=='['&&ch!=']' || ele=='{'&&ch!='}') {
					return false;
				}
			}
		}
	}
	return stack.isEmpty();
}
	public static void main(String[] args) {
		match test = new match();
		String s = "{[()]}";
		System.out.println(test.match1(s));
		System.out.println(test.match2(s));
		System.out.println(test.match3(s));
		System.out.println(test.match4(s));
	}

}
